package demo6;
import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    //1.对链表进行插入排序(四指针)
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0, head);//虚拟结点
        ListNode cur = head.next;//默认第一个有序，从第二结点开始
        ListNode pCur = head;//cur的上一个指针
        while(cur != null) {
            ListNode prev = dummy.next;//这个指针从头开始找，直达找到比他大的，然后插入到他的前面
            ListNode pprev = dummy;//prev的前一个
            //从头开始找比cur大的结点
            while(prev != cur && prev.val < cur.val) {
                pprev = prev;
                prev = prev.next;
            }
            if(prev == cur) {//此时就是他自己，就没必要交换
                pCur = cur;
                cur = cur.next;
                continue;
            }
            //再cur之前找到比cur大的结点，开始插入
            ListNode node = cur;//待插入的结点
            cur = cur.next;
            pCur.next = cur;
            pprev.next = node;
            node.next = prev;
        }
        return dummy.next;
    }
}
